/**
 * 面试题12：矩阵中的路径
 */
public class Offer_12 {
    /**
     * 回溯
     */
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || word == null) {
            return false;
        }
        int rows = board.length, cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 判断以网格的 <code>(i,j)</code> 位置出发，能否搜索到单词 word[k..]，
     * 其中 word[k..] 表示字符串 word 从第 k 个字符开始的后缀子串。
     * 如果能搜索到，则返回 <code>true</code>，反之返回 <code>false</code>。
     * 
     * <p>执行步骤：
     * <ul>
     *   <li>
     *     如果 <code>board[i][j] != s[k]</code>，当前字符不匹配，直接返回 false。
     *   </li>
     *   <li>
     *     如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 true。
     *   </li>
     *   <li>
     *     否则，遍历当前位置的所有相邻位置。
     *     如果从某个相邻位置出发，能够搜索到子串 word[k+1..]，则返回 true，
     *     否则返回 false。
     *   </li>
     * </ul>
     * <br>
     * 
     * @param board 题目给定的二维网格
     * @param visited 标识每个位置是否被访问过
     * @param i 
     * @param j 
     * @param word 待查找单词
     * @param k
     * @return
     */
    public boolean check(char[][] board, boolean[][] visited, int i, int j, String word, int k) {
        if (board[i][j] != word.charAt(k)) {
            return false;
        }
        if (k == word.length() - 1) {
            return true;
        }
        // 标记已访问位置
        visited[i][j] = true;
        // 四个方向
        int[][] directions = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };
        boolean ans = false;
        for (int[] direction : directions) {
            int newi = i + direction[0], newj = j + direction[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                // 如果未被访问过
                if (!visited[newi][newj]) {
                    boolean flag = check(board, visited, newi, newj, word, k + 1);
                    if (flag) {
                        ans = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return ans;
    }

    public static void main(String[] args) {
        Offer_12 solution = new Offer_12();
        char[][] board = { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'C', 'S' }, { 'A', 'D', 'E', 'E' } };
        String word = "ABCCED";
        boolean ans = solution.exist(board, word);
        System.out.println(ans);
        word = "ABCF";
        ans = solution.exist(board, word);
        System.out.println(ans);
    }
}
